//https://www.bilibili.com/video/BV1d54y1f7B3/?spm_id_from=333.337.search-card.all.click&vd_source=d6fe65f095f01f05591e89d810720ccc
// 2024-10-20

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class P022_二叉树的最小深度_广度优先 {

    public static void main(String[] args) {
        Tree node7 = new Tree(7,null,null);
        Tree node6 = new Tree(6,node7,null);
        Tree node5 = new Tree(5,null,null);
        Tree node4 = new Tree(4,null,null);
        Tree node3 = new Tree(3,node6,null);
        Tree node2 = new Tree(2,node4,node5);
        Tree node1 = new Tree(1,node2,node3);
        System.out.println(fun(node1));
    }

    //广度优先，顺序遍历，找到第一个叶子节点便是最小深度
    private static int fun(Tree root) {
        if (root == null) return 0;

        Queue<Tree> queue = new LinkedList<>();
        root.deep = 1;  //初始化深度
        queue.add(root);
        while (!queue.isEmpty()) {
            Tree temp = queue.poll();
            if (temp.left == null && temp.right == null) return temp.deep;//叶子节点
            if (temp.left != null)  {
                temp.left.deep = temp.deep + 1;
                queue.add(temp.left);
            }
            if (temp.right != null)  {
                temp.right.deep = temp.deep + 1;
                queue.add(temp.right);
            }
        }
        return -1;
    }


    static class Tree {
        int val;
        Tree left;
        Tree right;

        int deep;   //增加深度变量，用于记录深度

        public Tree(int val, Tree left, Tree right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
